package com.datastructure.tree.threadbinarytree.result2;

/**
 * @author Hacah
 * @date 2021/1/2 21:04
 * @Description 实现二叉树的中序线索化二叉树的第二种方法，把代码封装内部。
 */
public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {
        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree(1, "1");
        ThreadedBinaryTree.Node threeNode = binaryTree.addLeftChild(3, "3");
        threeNode.addLeftChild(8, "8");
        ThreadedBinaryTree.Node node10 = threeNode.addRightChild(10, "10");
        binaryTree.addRightChild(6, "6").addLeftChild(14, "14");

        // binaryTree.midOrder();

        // 测试
        binaryTree.threadedNode();
        // 查看node10左节点是否3，右节点是否是1
        System.out.println(node10.getLeftChild());
        System.out.println(node10.getRightChild());


    }


}

/**
 * 二叉树的类
 */
class ThreadedBinaryTree {

    /** 根节点 */
    private Node root;

    /** 保存前驱一个节点 */
    private static Node pre;

    public ThreadedBinaryTree(int no, String name) {
        root = new Node(no, name);
    }

    /**
     * 前序遍历
     */
    public void threadedNode() {
        root.threadedNode();
    }

    /**
     * 前序遍历方法
     */
    public void preOrder() {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("root为空");
        }
    }

    public void midOrder() {
        if (root != null) {
            root.midOrder();
        } else {
            System.out.println("root为空");
        }
    }

    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("root为空");
        }
    }

    /**
     * 添加左节点
     *
     * @return
     */
    public Node addLeftChild(int no, String name) {
        return root.addLeftChild(no, name);
    }

    /**
     * 添加右节点
     *
     * @return
     */
    public Node addRightChild(int no, String name) {
        return root.addRightChild(no, name);
    }


    /**
     * 二叉树的节点
     */
    static class Node {

        private int no;
        private String name;
        private Node leftChild;
        private Node rightChild;

        /** 用变量表示左指针指向的是哪个节点，如果是0为左节点，1为前序节点 */
        private int leftChildState;
        /** 用变量表示右指针指向的是哪个节点，如果是0为右节点，1为后序节点 */
        private int rightChildState;

        public Node(int no, String name) {
            this.no = no;
            this.name = name;
        }

        public Node getLeftChild() {
            return leftChild;
        }

        public Node getRightChild() {
            return rightChild;
        }

        public void threadedNode() {
            // 1.线索化左子树
            if (this.leftChild != null) {
                this.leftChild.threadedNode();
            }
            // 2.线索化本节点

            if (this.leftChild == null) {
                // 左节点指向前驱节点
                this.leftChild = pre;
                // 设置状态为指向前驱节点
                this.leftChildState = 1;
            }
            // 使用pre前节来操作右节点的线索化
            if (pre != null && pre.rightChild == null) {
                pre.rightChild = this;
                pre.rightChildState = 1;
            }
            // 当前值赋值给前节点，代表跟在node的后面
            pre = this;

            // 3.线索化右子树
            if (this.rightChild != null) {
                this.rightChild.threadedNode();
            }
        }


        /**
         * 前序遍历
         */
        public void preOrder() {
            System.out.println(this);
            if (this.leftChild != null) {
                leftChild.preOrder();
            }
            if (rightChild != null) {
                rightChild.preOrder();
            }
        }

        /**
         * 中序遍历
         */
        public void midOrder() {
            if (this.leftChild != null) {
                leftChild.midOrder();
            }
            System.out.println(this);
            if (this.rightChild != null) {
                rightChild.midOrder();
            }
        }

        /**
         * 后序遍历
         */
        public void postOrder() {
            if (this.leftChild != null) {
                leftChild.postOrder();
            }
            if (rightChild != null) {
                rightChild.postOrder();
            }
            System.out.println(this);
        }

        /**
         * 添加左节点
         *
         * @return
         */
        public Node addLeftChild(int no, String name) {
            Node node = new Node(no, name);
            this.leftChild = node;
            return node;
        }

        /**
         * 添加右节点
         *
         * @return
         */
        public Node addRightChild(int no, String name) {
            Node node = new Node(no, name);
            rightChild = node;
            return node;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    '}';
        }

    }

}

